1. Field of the Invention
The present invention relates to an optimization apparatus which removes transfer instructions and replaces operands.
2. Description of the Prior Art
In recent years, a great number of information devices which use embedded microprocessors have been developed to meet a variety of needs. The software side of the development of such devices has focused on the acceleration of processing and the reduction of hardware cost (here, measured in terms of memory size). For embedded processors, programs have to be stored in ROM, so that increases in program size can greatly affect manufacturing cost. Consequently, programs used by embedded microprocessors need to be completely relieved of redundant transfer instructions and to be developed in assembly language to make the greatest possible use of microprocessor functions, such as addressing mode. However, the syntax rules used in assembly language are the instruction system of the processor itself, so that software development hag conventionally been inefficient and has had problems concerning portability.
Improvements in the efficiency of software development for embedded microprocessors have been conventionally achieved by developing software in a high-level programming language. This method, however, has the drawback that a large number of redundant instructions are generated when the program is compiled into machine language, leading to an increase in the memory size of the generated software.
The following is an explanation of why machine language programs which have been generated from a high-level programming language are large, with reference to FIG. 1. In FIG. 1, the machine language instructions corresponding to calculations written in a high-level programming language have been shown using a curved bracket "{".
In FIG. 1, the sequence of instructions from "mov 1, (sp+4)" to "jsr.sub.-- f2" corresponds to the function call instruction "f2(1,2);" in the source program. This shows that in the present example, a subroutine call instruction for the subroutine f2 is translated into the three instructions, "mov 1, (sp+4)" to "jsr.sub.-- f2".
In the same way, the sequence of instructions from "mov (sp+24), r1", "mov (sp+20), r2" to "add r1, r2", "mov r2, (sp+4)" corresponds as shown by the curved bracket to the instruction "a=p1+p2". This shows that the addition instruction "a=p1+p2" that uses variables which are only used in subroutine f2 is translated into four instructions made up of "mov (sp+24), r1" to "add r1, r2" and "mov r2, (sp+4)".
As another example, the sequence of instructions from "mov (sp+24), r1" to "sub r2, r1", "mov r1, (sp)" corresponds as shown by the curved bracket to "b=p1-p2". This shows that the subtraction instruction "b=p1-p2" which uses the automatic variable in subroutine f2 is translated into four instructions made up of "mov (sp+24), r1"to "sub r2, r1" and "mov r1, (sp)".
As described above FIG. 1 shows that the relationship between calculations written in high-level programming language and machine language instructions is a one-to-many relationship. From FIG. 1, it can be seen that a number of "mov" transfer instructions are generated to perform the calculations written in the high-level processing language. These transfer instructions include redundant instructions and instructions which could be omitted if the program were better written.
Since a plurality of transfer instructions are generated during compiling, there have been demands for optimization of the machine language instructions which result from the translation of high-level programming language instructions. Here, there have been especially strong demands for optimization of development efficiency and memory size when developing programs for embedded microprocessors. As conventional methods, propagation processing and convolution can improve the execution time and memory size of machine language instructions, while redundant code can be removed according to a method which removes redundant instructions which use equivalence relations.
The following is an explanation, with reference to FIG. 2, of this method which removes redundant instructions that use equivalence relations. Here, FIG. 2 shows the changes in the equivalence relations due to the execution of each instruction in a basic block.
When a program is rewritten, there is a risk that the algorithm will be destroyed due to the rewriting of jump instructions in the middle of a sequence or instructions which are the jump destinations in the middle of a sequence. As a result, optimization has only been possible when the execution order of the program is continuous. Here, sequences of consecutive instructions which do not feature a branch to another sequence and sequences of consecutive instructions which are not branched to by other sequences are called "basic blocks", and are used as the basic unit during optimization.
In the example program shown in FIG. 2, the branch instruction "bra L4" expresses a branch to the label L4. The conditional branch instruction "bne L3" is a branch instruction whose execution depends on the state of the zero flag, so that a branch to label L3 is performed when the zero flag is "0". Due to the existence of this conditional branch instruction "bne L3" and the branch instruction "bra L4", the program cannot be optimized in its initial state. As a result, the program is divided into basic blocks based on the branch instructions and their branch address labels.
In the example program shown in FIG. 2, the sequence of instructions from the transfer instruction "mov #10, D0.sub.-- (1)" to the conditional branch instruction "bne L3.sub.-- (5)" is set as one basic block. In the same way the sequence of instructions from the transfer instruction "mov (2, SP), D1.sub.-- (6)" to the branch instruction "bra L4.sub.-- (11)" set as another basic block. The sequence of instructions from the transfer instruction "mov (10, SP), D1.sub.-- (12)," onwards includes the label L4 which is the branch address of the branch instruction "bra L4.sub.-- (11)". Here, since the label L4 is attached to the transfer instruction "mov #100, D1.sub.-- (16)", the sequence of instructions from the transfer instruction "mov (10,SP), D1.sub.-- (12)" to the transfer instruction "mov D0, A0.sub.-- (15)" is set as one basic block and the sequence of instructions from the transfer instruction "mov #100, D1.sub.-- (16)" to the transfer instruction "mov (4,SP), D0.sub.-- (21)" is set as another basic block.
After dividing the program into basic blocks in this way, equivalence relations in each block are investigated. Here, if the position before the first instruction of a basic block, the position between two adjacent instructions, and the position after the final instruction in a basic block are set as "points", then equivalence relations are defined as the state when, at a given point in the program, the value held by one resource is the same as that held by another resource. As one example, if the value of the register D0 is the same as the value of the register A0 at point A, then register D0 and register A0 are said to exhibit an equivalence relation at point A, while if, at point B, register D1 is holding the immediate value 10, then register D1 and the immediate value 10 are said to exhibit an equivalence relation.
In the table on the right-hand side of FIG. 2, a table shows the transfer instruction "mov (2,SP), D1.sub.-- (6)", the subtraction instruction "sub #1, D1.sub.-- (7)", the transfer instruction "mov D1, (2,SP).sub.-- (8)", the transfer instruction "mov (2,SP), D1.sub.-- (9)", etc., with a further column showing the registers "D0=", D1=", and "A0=" for each instruction. This column shows the equivalence relations exhibited by these registers after each of the instructions in this basic block is executed.
The transfer instruction "mov (2,SP), D1.sub.-- (6)" transfers the value held in the memory region indicated by (2,SP) into the data register D1. Here, the memory region (2,SP) is a region which is two places past the value of the stack pointer. In FIG. 2, D1=(2,SP) is written to the right of the transfer instruction "mov (2,SP), D1.sub.-- (6)" showing that the data register D1 and the stack (2,SP) exhibit an equivalence relation after the transfer instruction "mov (2,SP), D1.sub.-- (6)" has been executed. In this way, the equivalence relations after this instruction can be understood.
The subtraction instruction "sub #1, D1.sub.-- (7)" subtracts "1" from the stored value of the data register D1. While D1=(2,SP) is written to the right of the transfer instruction "mov (2,SP), D1.sub.-- (6)", this is no longer valid after the subtraction instruction "sub #1, D1.sub.-- (7)". This is to say, the execution of the subtraction instruction "sub #1, D1.sub.-- (7)" reduces the value of the data register D1, and by doing so destroys the equivalence relation of the data register D1 with the stack (2,SP).
The transfer instruction "mov D1, (2,SP).sub.-- (8)" transfers the value held by the data register D1 into the stack region indicated by the address (2,SP) In FIG. 2, "D1=(2,SP)" is written to the right of the transfer instruction "mov D1, (2,SP).sub.-- (8)" showing that the data register D1 and the stack (2,SP) exhibit an equivalence relation after the transfer instruction "mov D1, (2,SP).sub.-- (8)" has been executed.
The transfer instruction "mov (2,SP), D1.sub.-- (9)" transfers the value held by the stack region (2,SP) into the data register D1. In FIG. 2, "D1=(2,SP)" is written to the right of the transfer instruction "mov (2,SP), D1.sub.-- (9)" showing that the data register D1 and the stack (2,SP) exhibit an equivalence relation after the transfer instruction "mov (2,SP), D1.sub.-- (9)" has been executed.
The transfer instruction "mov D0, A0.sub.-- (10)" transfers the value held by the data register D0 into the address register A0. In FIG. 2, "D0=A0", "D1=(2,SP)", and "A0=D0" are written to the right of the transfer instruction "mov D0, A0.sub.-- (10)" showing that an equivalence relation between the data register D0 and the address register A0 is generated when the transfer instruction "mov D0, A0.sub.-- (10)" is executed.
By clearly establishing the equivalence relations as shown above, it can be seen that the transfer instruction "mov (2,SP), D1.sub.-- (9)" performs a transfer of a value regardless of the equivalence relation created by the transfer instruction "mov D1, (2,SP).sub.-- (8)", by which the destination resource can be seen to already store the transferred value. Accordingly, since an equivalence relation has been established by the transfer instruction "mov D1, (2,SP).sub.-- (8)", the transfer instruction "mov (2,SP), D1.sub.-- (9)" is redundant. When redundant instructions, such as this transfer instruction "mov (2,SP), D1.sub.-- (9)", with equivalence relations are detected, they can be deleted from the program.
As described above, equivalence relations are analyzed for each basic block and the redundant instructions are deleted from the program, reducing the total number of instructions in the program, and improving the memory size and execution time of the program.
Problem which the Present Invention is Attempting to Solve
Conventionally, there has been the problem that since the analysis of equivalence relations has not been allowed to exceed the boundaries of each basic block, redundant instructions have been left undeleted, which has limited the extent to which memory size and execution time can be improved. This is explained in more detail with reference to FIGS. 3 to 5. FIG. 3 shows a redundant transfer instruction in the example of FIG. 2 which will most probably not be deleted, FIG. 4 shows a pattern (deletion prohibited pattern) for the transfer instruction "mov A0, D0.sub.-- (17)" of FIG. 3 by which it may not be deleted, and FIG. 5 shows a pattern (deletion possible pattern) by which for the transfer instruction "mov A0, D0.sub.-- (17)" of FIG. 3 may be deleted.
In FIG. 3, the circled transfer instruction "mov A0, D0.sub.-- (17)" in basic block 4 is a transfer instruction between resources A0 and D0 which already exhibit equivalence relations This equivalence relation between the address register A0 and the data register D0 is established by the transfer instruction "mov A0, D0.sub.-- (10)" in the basic block B2 and the transfer instruction "mov A0, D0.sub.-- (15)" in the basic block B3. Here, so long as no addition instruction or subtraction instruction which affects the values held by the address register A0 or the data register D0 is present between the transfer instruction "mov A0, D0.sub.-- (10)" and the transfer instruction "mov A0, D0.sub.-- (17)", or between the transfer instruction "mov A0, D0.sub.-- (15)", and the transfer instruction "mov A0, D0.sub.-- (17)", then the transfer instruction "mov A0, D0.sub.-- (17)" in FIG. 3 will be a redundant instruction which may be deleted.
On the other hand, in FIGS. 4 and 5. basic blocks M1 and M2 follow these basic blocks, with a branch instruction to basic block B4 being placed at the end of these basic blocks. FIG. 4 shows that four routes to the basic block B4 are possible due to these branch instructions, with route (1) being a branch from basic block B2, route (2) being a branch from basic block B3, route (3) being a branch from basic block M1, and route (4) being a branch from basic block M2. The following is an explanation of how the equivalence relation between address register A0 and the data register D0 is affected by these various routes, with reference to FIG. 5. In the example shown in FIG. 5, the transfer instructions "mov D0, A0.sub.-- (31)", "mov D0, A0.sub.-- (32)" are respectively positioned at the end of basic blocks M1, M2. As a result, the transfer instruction "mov A0, D0.sub.-- (17)" can be deleted.
In the example in FIG. 4, however, transfer instructions "mov D1, A0.sub.-- (31)" and "mov #30, A0.sub.-- (32)" which set a different value in register A0 are present at the respective ends of basic blocks M1 and M2. If the transfer instruction "mov A0, D0.sub.-- (17)" is deleted in this case, the setting of the stored value of the data register D0 goes astray and destroys the algorithm in the program. As a result, the transfer instruction "mov A0, D0.sub.-- (17)" a cannot be deleted
When deleting equivalence relations between basic blocks, it is first necessary to judge whether the deletion prohibited pattern shown in FIG. 4 or the deletion possible pattern shown in FIG. 5 is present. However, it can be very difficult to ascertain the execution order of machine language programs due to the existence of branch instructions, so that the patterns of FIG. 4 or FIG. 5 cannot be recognized. As a result, even when there is a large incidence of the deletion possible pattern of FIG. 5 after translation by a compiler, the redundant instructions cannot be deleted. As a result, the deletion of all deletable transfer instructions has not been possible. In the same way as the method for the deletion of redundant instructions involving equivalence relations, methods for the improvement of machine language programs using copy propagation are restricted to optimization which is limited by the boundaries of each basic block to protect the program algorithm. As a result, such methods will not be effective for the case of equivalence relations between basic blocks which was shown in FIG. 5.